The Open Shortest Path First (OSPF) protocol is a link-state routing protocol used for internet routing. OSPF is described in detail by Moy in “OSPF Version 2, published as Request for Comments (RFC) 2328 of the Internet Engineering Task Force (IETF) Network Working Group (April, 1998), which is incorporated herein by reference. This document is available at www.ietf.org, as are the other IETF RFC and draft documents mentioned below. OSPF is used by a group of Internet Protocol (IP) routers in an Autonomous System to exchange information regarding the system topology. (The term “Autonomous System” is used in the art to denote a group of routers exchanging routing information via a common routing protocol.) Each OSPF router maintains an identical topology database. Based on this database, the routers calculate their routing tables by constructing a shortest-path tree to each of the other routers.
Each individual piece of the topology database maintained by the OSPF routers describes the local state of a particular router in the Autonomous System. This “local state” includes information such as the router's usable interfaces and reachable neighbors. The routers distribute their local state information by transmitting a link state advertisement (LSA). Packets containing link state advertisements are flooded throughout the routing domain. The other routers receive these packets and use the LSA information to build and update their databases.
OSPF routes IP packets based solely on the destination IP address in the IP packet header. A cost is associated with the output side of each router interface and is used by the router in choosing the least costly path for the packets. This cost is configurable by the system administrator. The lower the cost, the more likely the interface is to be used to forward data traffic. For the purposes of cost calculation and routing, OSPF recognizes two types of “networks” (which may be organized as IP networks, subnets or supernets): point-to-point networks, which connect a single pair of routers; and multi-access networks, supporting many (two or more) attached routers. Each pair of routers on a multi-access network is assumed to be able to communicate directly with one another. An Ethernet is an example of a multi-access network. Each multi-access network includes a “designated router,” which is responsible for generating LSAs, as well as certain other protocol functions.
FIGS. 1 and 2 are schematic illustrations of OSPF networks, illustrating how link costs are assigned and computed in such networks. FIG. 1 shows three routers 20, labeled, R1, R2 and R3 , connected by point-to-point networks 22. Each interface of each of the routers has its own cost, which is shown in the figure at the point of connection of each of routers 20 to each of networks 22. It will be seen that different directions on the same point-to-point network can have different costs assigned to them. Based on these costs, for example, R3 will choose to route packets to R1 via R2, since the cost of this path is 3+9=12, which is less than the cost (15) of sending the packets from R3 to R1 directly.
In FIG. 2, routers 20 are connected by a multi-access network, represented by a hub 24 through which every router is considered to communicate with every other router. The hub may be real or virtual, depending on the underlying physical structure of the network, but this distinction is not recognized by OSPF. In the multi-access network, there is a single cost assigned to the network interface of each router, so that the cost of communicating with any of the other routers in the network is the same. Thus, for example, the cost of routing packets from R1 to either R2 or R3 is 7. OSPF does not recognize or assign costs to any different paths that may exist between nodes within the multi-access network.
Traffic engineering (TE) is concerned with performance optimization of operational networks, typically by controlling Internet traffic to achieve specific performance objectives. The principles and objectives of TE are described, for example, by Awduche et al., in “Requirements for Traffic Engineering Over MPLS,” published as IETF RFC 2702 (September, 1999), which is incorporated herein by reference. Internet traffic engineering attempts to facilitate efficient and reliable network operations while simultaneously optimizing network resource utilization and traffic performance. TE has become an indispensable function in many large Autonomous Systems because of the high cost of network assets and the commercial and competitive nature of the Internet. Key traffic-oriented performance objectives include minimization of packet loss, minimization of delay, maximization of throughput, and enforcement of service level agreements. Resource-oriented TE functions include load-balancing and efficient bandwidth management, to ensure that subsets of network resources do not become overutilized and congested while other subsets along alternate feasible paths remain underutilized.
Although OSPF allows the system administrator to assign interface costs, as described above, this feature is not sufficient to support full TE-based routing in an Autonomous System. For this purpose, Katz et al. suggest extending the link state attributes of OSPF, in an IETF Internet Draft entitled “Traffic Engineering Extensions to OSPF,” (draft-katz-yeung-ospf-traffic-06.txt, October, 2001), which is incorporated herein by reference. The OSPF TE extensions described by Katz et al. can be used to build an extended link state database, which can then be used for global traffic engineering, as well as local constraint-based routing.
In order to distribute the extended OSPF link attributes among the routers, Katz et al. define a new LSA type and a number of Type/Length/Value (TLV) triplets that can be included in the payload of a LSA. Each LSA contains one top-level TLV, which identifies either a router or a link. For link TLVs, Katz et al. define a set of sub-TLVs, which can be used to advertise TE-related constraints on the link, as shown below in Table I:
TABLE ILINK SUB-TLVS IN OSPF-TETLVtypeNameDescription1Link typePoint-to-point or multi-access2Link IDIdentifies the neighboring router at theother end of the link. (The advertisingrouter is identified in the LSA header.)3LocalIP address(es) of the interfaceinterfacecorresponding to this link. (If there areIP addressmultiple local addresses on the link,they are all listed in this sub-TLV.)4RemoteIP address(es) of the neighbor'sinterfaceinterface corresponding to this link.IP address5TrafficLink metric for TE purposes - may be theengineeringsame as or different from the standardmetricOSPF link metric.6MaximumMaximum bandwidth that can be used onbandwidththis link in this direction (from theadvertising router to its neighbor).7MaximumMaximum bandwidth that may be reserved onreservablethis link - may be greater than thebandwidthmaximum bandwidth if the link isoversubscribed.8UnreservedAmount of bandwidth not yet reserved atbandwidtheach of eight different priority levels.9ResourceSpecifies administrative group membershipclass/colorfor this link, in terms of a bit mask.Further details of the LSA and TLV format are described in the above-mentioned draft.
Bi-directional network ring topologies are gaining in popularity, particularly in Internet Protocol (IP) networks. Such networks provide efficient bandwidth utilization by enabling data to be transferred between any pair of nodes in either direction around the ring, while maintaining fast protection against faults. The two opposing traffic directions are commonly referred to as an inner ring and an outer ring. It will be understood, however, that in the context of the present patent application and in the claims, the terms “inner” and “outer,” as well as “clockwise” and “counterclockwise,” are used arbitrarily to distinguish between the two opposing directions of packet flow in a ring network. These terms are chosen solely for convenience of explanation, and do not necessarily bear any relation to the physical characteristics of the network.
The leading bi-directional protocol for high-speed packet rings is the Resilient Packet Rings (RPR) protocol, which is in the process of being defined as IEEE standard 802.17. Network-layer routing over RPR is described, for example, by Jogalekar et al., in “IP over Resilient Packet Rings” (Internet Draft draft-jogalekar-iporpr-00), and by Herrera et al., in “A Framework for IP over Packet Transport Rings” (Internet Draft draft-ietf-ipoptr-framework-00). A proposed solution for Media Access Control (MAC—protocol layer 2) in bidirectional ring networks is the Spatial Reuse Protocol (SRP), which is described by Tsiang et al., in IETF RFC 2892. These documents are incorporated herein by reference.
Using protocols such as these, each node in a ring network can communicate directly with all other nodes through either the inner or the outer ring, using the appropriate Media Access Control (MAC) addresses of the nodes. Each packet sent over one of the rings carries a header indicating its destination node. The destination node recognizes its address in the header and strips the packet from the ring. All other nodes pass the packet onward transparently around the ring. Multicast packets may also be delivered over the rings in a similar fashion. Thus, the bi-directional ring can be regarded as a multi-access network for the purposes of OSPF.
In terms of traffic engineering, however, there are basic differences between bi-directional ring networks and legacy multi-access networks, such as Ethernets. For example, a packet transmitted on the ring network does not load the bandwidth of the entire network, as in legacy networks, but rather loads only the segments between the source and destination nodes on the ring (inner or outer) over which the packet travels. This feature of the ring network is an important consideration in traffic engineering and should be taken into account in routing of packets through the ring network. OSPF (including the extensions proposed by Katz et al.), however, provides no facilities for advertising or using information regarding segments within a multi-access network.